package org.example.algorithm.dp;

public class LengthOfLISSolution {
    public static void main(String[] args) {
        //int[] nums = {0,1,0,3,2,3};
        int[] nums = {3,5,6,2,5,4,19,5,6,7,12};
        LengthOfLISSolution lengthOfLISSolution = new LengthOfLISSolution();
        int res = lengthOfLISSolution.lengthOfLIS(nums);
        System.out.println(res);
    }

    /**
     * 动态规划
     * dp[i]代表以i为结尾的最大递增子序列长度,其中nums[i]必须选中
     * dp[i] = Math.max(dp[j]) + 1;(0=<j<i)
     * @param nums
     * @return
     */
    public int lengthOfLIS2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = dp[0];
        for (int i=1;i<nums.length;i++) {
            dp[i] = 1;
            for (int j=0;j<i;j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    //cell中存储的是各个长度的子序列的最小结尾
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] minTail = new int[nums.length];
        minTail[0] = nums[0];
        int index = 0;
        for (int i=1;i<nums.length;i++) {
            if (nums[i] > minTail[index]) {
                index++;
                minTail[index] = nums[i];
            } else {
                int low = 0;
                int high = index-1;
                boolean flag = false;
                while (low <= high) {
                    int middle = (low + high) / 2;
                    if (minTail[middle] < nums[i]) {
                        low = middle + 1;
                    } else if(minTail[middle] > nums[i]) {
                        high = middle - 1;
                    } else {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    minTail[low] = nums[i];
                }
            }
        }
        return index+1;
    }
}
